#define ElemType int

#include "common.h"

int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes);

int main()
{
	return 0;
}

int cmp(const void* a, const void* b)
{
	int *o1 = *(int**)a, *o2 = *(int**)b;
	return o1[0] - o2[0];
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes)
{
	//printf("%d\n", **intervals);
	//printf("%d\n", intervalsSize);
	//printf("%d\n", *intervalsColSize);
	//printf("%d\n", *returnSize);

	qsort(intervals, intervalsSize, sizeof(int*), cmp);

    *returnColumnSizes = malloc(sizeof(int) * intervalsSize);
	int** res = calloc(intervalsSize, sizeof(int*));

	int lo = intervals[0][0], hi = intervals[0][1], size = 0;
	for (int i = 1; i < intervalsSize; i++) {
		if (intervals[i][0] <= hi)
			hi = hi > intervals[i][1] ? hi : intervals[i][1];
		else {
			returnColumnSizes[0][size] = 2;
			res[size] = malloc(2 * sizeof(int));
			res[size][0] = lo, res[size][1] = hi;
			size++;

			lo = intervals[i][0], hi = intervals[i][1];
		}
	}

	returnColumnSizes[0][size] = 2;
	res[size] = malloc(2 * sizeof(int));
	res[size][0] = lo, res[size][1] = hi;
	*returnSize = ++size;

	return res;
}
